class DBNode{
    //每一个节点的结构
    constructor(value) {
        this.value = value //数据域
        this.next = undefined //下一个指针域
        this.pre = undefined //上一个指针域
    }
}

class LinkedList{
    constructor() {
        this.count = 0 //计数器
        this.head = undefined //链头，起始节点
    }

    push(value){ //在尾部新增一个值
        let node = new DBNode(value) //实例生成节点对象
        let pre = this.head
        let current //当前遍历的节点
        if(!this.head){
            this.head = node
            //如果说当前链表里是空的，就说明head也是空的，那就直接把新增的设置为链表的第一个
        }else{ //如果链表第一个不为空，那我们就往后面数
            current = this.head //链表头为当前已经遍历的节点
            while(current.next){ //如果当前节点的指针域所指向的地方不为空的时候，说明它还不是最后一个节点，就继续循环遍历
                current = current.next //只要不是最后一个节点，就一直把当前所遍历到的那个节点的指向，指向下一个
                pre = current //pre必须指向当前这个节点，这样当前节点后面新增的一个node的pre才能指向上一个节点（也就是当前节点）
            }
            current.next = node //如果遍历到了最后一个节点，跳出了循环，那么就把当前的指针域指向这被遍历到的最后一个节点
            node.pre = pre //新增节点的前一个指针域指向当前节点（看上面两行代码）
        }
        this.count++ //当在尾部添加完一个新值之后，计数器加一
    }

    removeAt(index){ //删除链表上面的第几个数据
        if(index >= 0 && index < this.count){ //如果要删除一个指定的数据，必须满足下标大于等于0且小于链表长度这两个条件
            let current = this.head
            let beRemoved //被删除的
            if(index = 0){ //如果删除的是第0个，链头
                beRemoved = current
                this.head = current.next //链头指向下一个数据，那么原来的链头数据就被删除了
                this.head.pre = undefined
                //当原来链表头被删除，原来的第1位成为新的链表头，但原来的第1位的pre是有值的指向被删除的那个节点，所以需要将原来的指向undefined清空
            }else{ //这一步循环非常难理解，可以试着代入具体的数值0 1 2 3 4来理解
                for(let i = 1; i < index; i++){ //为啥从1开始，因为刚刚已经排除了第0位
                    current = current.next //当循环结束时，要被删除节点的前一个节点，i-1
                }
                beRemoved = current.next //待删除的节点，i，（current.next）.next
                current.next.next.pre = current
                //由上一行代码可知current.next指向被删除的节点，那么current就是被删除节点的前一个节点，
                //所以被删除节点的下一个节点的上一个指针域指向被删除节点的前一个节点current

                current.next = current.next.next //当前节点的前一个节点的指针域 指向 当前节点的下一个节点，那么当前节点就被删除了
            }
            this.count--
            return beRemoved
        }
    }

    removeValue(value){ //删除链表中指定值的节点
        let current = this.head
        let pre = null //被删除节点的前一个节点
        if(current.value === value){ //如果输入的值与链头的值相等
            this.head = current.next
            this.head.pre = undefined //同上面removeAt的道理一样
        }else{
            for(let i =1; i < this.count; i++){
                pre = current //将i-1保存到变量pre
                current = current.next //需要被删除的节点i
                if(current.value === value){
                    pre.next = current.next //前一个节点（i-1）的指针域 指向 需要被删除的节点（i）的指针域所指向的节点（i+1）
                    current.next.pre = pre
                    //注意前三行代码写了current变量保存了需要被删除的节点i，被删除节点的下一个节点的前一个指针域指向被删除节点的前一个节点pre（i-1）
                    break //删除符合条件的第一个值，如果没写break就是继续循环，删除符合条件的所有值
                }
            }
        }
        this.count--
    }

    pop(){ //模拟pop功能，删除最后一个
        return this.removeAt(this.count - 1)
    }

    indexOf(value){ //查询一个值在链表里面的位置，返回该值的位置下标
        let current = this.head
        if(value === current.value){ //三个等号全等，数据类型也要相同
            return 0
        }

        //如果不是第0位，那么就进入下面这个循环
        for(let i = 1; i < this.count; i++){
            current = current.next //不是第0位，那么就一直循环往后挪
            if(value === current.value){
                return i
            }
        }
        return undefined //如果既不是if里面的，也不是for循环里面的，那就说明找不到，找不到就返回undefined
    }

    getNodeAt(index){ //获取指定位置的值
        if(index >=0 && index < this.count){
            let current = this.head
            if(index === 0){
                return current
            }else{
                for(let i =1; i < index; i++){
                    current = current.next //当循环结束时，被剔除的节点的前一个节点
                }
                return current.next
            }
        }
    }

    insert(value,index){ //指定位置插入新节点
        let node = new DBNode(value)
        if(index >= 0 && index <= this.count){ //输入的索引值在链表长度内
            let current = this.head //先把原来开头的值保存下来
            if(index === 0){ //插入开头
                this.head = node
                this.head.next = current //把新的开头值的指针域 指向 原先开头的值
                current.pre = this.head //原先开头的值得前一个指针域指向最新的开头值
            }else{
                for(let i = 1; i < index; i++){
                    current = current.next //当循环结束时，插入新节点的位置 的 前一个节点 等号左边的current变量是i-1
                }
                let nextEle = current.next //nextEle保存原来的i
                current.next = node //i-1的指针域指向新插入的节点
                node.next = nextEle //新插入的节点的指针域指向原来的i

                node.pre = current
                //当插入第1位的时候，i=1，1不小于1所以不走for循环，所以current还是this.head，新插入的node节点的前一个指针域指向this.head
                nextEle.pre = node
                //原先在第1位的节点nextEle的前一个指针域pre指向最新插入的node节点

                this.count++
            }
        }else{ //输入的索引值超出链表长度
            throw new Error("索引值错误")
        }
    }

    isEmpty(){
        return !this.count
    }

    size(){
        return this.count
    }

    getHead(){
        return this.head.value
    }

    toString(){
        let objString = ""
        let current = this.head
        if(!current){ //如果链表头不存在
            return "" //返回空
        }else{
            do{ //至少会先执行一次do里面的循环
                objString = `${objString},${current.value}`
                current = current.next
            }while(current) //只要还有当前值，就一直进行do里面的循环
            return objString.slice(1)
        }
    }
}

let linkData = new LinkedList()